package nowcoder;

/**
 * 求找零钱的有多少种组合
 * @author tuyou_cd
 * @date 2021/4/29 14:22
 */
public class 找零钱组合 {

    /**
     * 暴力求解法
     * @param arr
     * @param aim
     * @return
     */
    public static int violenceCompute(int[] arr, int aim) {
        return violenceCompute(arr, aim, 0);
    }

    public static int violenceCompute(int[] arr, int aim, int index) {
        int count = 0;
        if (index == arr.length) {
            count = aim == 0 ? 1 : 0;
        } else {
            for (int piece = 0; piece * arr[index] <= aim; piece++) {
                count += violenceCompute(arr, aim - piece * arr[index], index + 1);
            }
        }
        return count;
    }

    /**
     * 动态规划法
     * @param arr
     * @param aim
     * @return
     */
    public static int dpCompute(int[] arr, int aim) {
        int[][] dp = new int[arr.length][aim + 1];

        //先赋值第一列，全是1
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }
        //再赋值第一行
        for (int i = 1; i * arr[0] <= aim; i++) {
            dp[0][ i * arr[0]] = 1;
        }

        //给所有元素赋值
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
            }
        }

        return dp[arr.length - 1][aim];
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,4};
        int aim = 3;
        System.out.println(violenceCompute(arr, aim));
        System.out.println(dpCompute(arr, aim));
    }
}
